package ai;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.concurrent.LinkedBlockingQueue;

public class 八数码广度优先搜索 {

    //close表
    static ArrayList<Node> close = new ArrayList<>();

    private static Node BFS(Node start, int[][] target){

        //open表
        LinkedBlockingQueue<Node> open = new LinkedBlockingQueue<>();

        //将start放入open表中
        open.offer(start);

        //open表不为空则进行搜索
        while (!open.isEmpty()) {
            //取open表第一个节点放到close表中，注意这里没有进行对已经查找过的不再进行查找的优化
            Node nowNode = open.poll();

            if (closeContains(nowNode.node)) continue;

            //如果当前节点为目标节点，返回搜索成功
            if (arrayEquals(nowNode.node, target)) return nowNode;

            close.add(nowNode);

            Node leftNode = moveLeft(nowNode);
            Node rightNode = moveRight(nowNode);
            Node upNode = moveUp(nowNode);
            Node downNode = moveDown(nowNode);

            if (!arrayEquals(leftNode.node, nowNode.node)) {
                open.offer(leftNode);
            }

            if (!arrayEquals(rightNode.node, nowNode.node)) {
                open.offer(rightNode);
            }

            if (!arrayEquals(upNode.node, nowNode.node)) {
                open.offer(upNode);
            }

            if (!arrayEquals(downNode.node, nowNode.node)) {
                open.offer(downNode);
            }
        }

        return null;
    }

    /**
     * 找到空白节点的位置
     * @param node  当前状态
     * @return      0是y坐标，1是x坐标
     */
    private static int[] findZero(Node node){
        int[] result = new int[2];

        for (int x = 0;x < 3;x++) {
            for (int y = 0;y < 3;y++) {
                if (node.node[x][y] == 0) {
                    result[0] = x;
                    result[1] = y;
                    return result;
                }
            }
        }

        return result;
    }

    /**
     * 向左移动
     * @param node  当前状态
     * @return      移动后状态
     */
    private static Node moveLeft(Node node){
        int[] position = findZero(node);

        //空白位于最右边是无法让相邻元素向左移动的
        if (position[1] == 2) return node;

        int[][] newArray = new int[3][3];
        for (int x = 0;x<3;x++) {
            System.arraycopy(node.node[x], 0, newArray[x], 0, 3);
        }

        //配上父节点
        Node newNode = new Node(newArray, node);

        newNode.node[position[0]][position[1]] = newNode.node[position[0]][position[1] + 1];
        newNode.node[position[0]][position[1] + 1] = 0;

        return newNode;
    }

    /**
     * 向右移动
     * @param node  当前状态
     * @return      移动后状态
     */
    private static Node moveRight(Node node){
        int[] position = findZero(node);

        //空白位于最左边是无法让相邻元素向右移动的
        if (position[1] == 0) return node;

        int[][] newArray = new int[3][3];
        for (int x = 0;x<3;x++) {
            System.arraycopy(node.node[x], 0, newArray[x], 0, 3);
        }

        //配上父节点
        Node newNode = new Node(newArray, node);

        newNode.node[position[0]][position[1]] = newNode.node[position[0]][position[1] - 1];
        newNode.node[position[0]][position[1] - 1] = 0;

        return newNode;
    }

    /**
     * 向上移动
     * @param node  当前状态
     * @return      移动后状态
     */
    private static Node moveUp(Node node){
        int[] position = findZero(node);

        //空白位于最下边是无法让相邻元素向上移动的
        if (position[0] == 2) return node;

        int[][] newArray = new int[3][3];
        for (int x = 0;x<3;x++) {
            System.arraycopy(node.node[x], 0, newArray[x], 0, 3);
        }

        //配上父节点
        Node newNode = new Node(newArray, node);

        newNode.node[position[0]][position[1]] = newNode.node[position[0] + 1][position[1]];
        newNode.node[position[0] + 1][position[1]] = 0;

        return newNode;
    }

    /**
     * 向下移动
     * @param node  当前状态
     * @return      移动后状态
     */
    private static Node moveDown(Node node){
        int[] position = findZero(node);

        //空白位于最上边是无法让相邻元素向下移动的
        if (position[0] == 0) return node;

        int[][] newArray = new int[3][3];
        for (int x = 0;x<3;x++) {
            System.arraycopy(node.node[x], 0, newArray[x], 0, 3);
        }

        //配上父节点
        Node newNode = new Node(newArray, node);

        newNode.node[position[0]][position[1]] = newNode.node[position[0] - 1][position[1]];
        newNode.node[position[0] - 1][position[1]] = 0;

        return newNode;
    }

    /**
     * 判断二维数组是否相等
     * @param a 数组a
     * @param b 数组b
     * @return 是否相等
     */
    private static boolean arrayEquals(int[][] a, int[][] b) {
        for (int i = 0;i<3;i++) {
            for (int j = 0;j<3;j++) {
                if (a[i][j] != b[i][j]) return false;
            }
        }
        return true;
    }

    /**
     * close表中是否包含当前二维数组
     * @param a 当前二维数组
     * @return  是否包含
     */
    private static boolean closeContains(int[][] a) {
        for (Node node : close) {
            if (arrayEquals(node.node, a)) return true;
        }
        return false;
    }

    private static void printResult(Node target) {
        if (target != null) {
            System.out.println(target);

            Node node = target.parent;

            while (node != null) {
                System.out.println(node);
                node = node.parent;
            }
        } else {
            System.out.println("没有结果");
        }
    }

    public static void main(String[] args) {
        int[][] s = new int[3][3];
        int[][] t = new int[3][3];

        s[0][0] = 2;
        s[0][1] = 8;
        s[0][2] = 3;
        s[1][0] = 1;
        s[1][1] = 6;
        s[1][2] = 4;
        s[2][0] = 7;
        s[2][1] = 0;
        s[2][2] = 5;

        t[0][0] = 1;
        t[0][1] = 2;
        t[0][2] = 3;
        t[1][0] = 8;
        t[1][1] = 0;
        t[1][2] = 4;
        t[2][0] = 7;
        t[2][1] = 6;
        t[2][2] = 5;

        Node start = new Node(s, null);

        Node target = BFS(start, t);

        printResult(target);
    }

    /**
     * 定义节点内容
     */
    static class Node{
        //二维数组表示八数码，0代表空白
        public int[][] node;

        //指向父节点
        public Node parent;

        public Node(int[][] node, Node parent) {
            this.node = node;
            this.parent = parent;
        }

        @Override
        public String toString() {
            return  Arrays.toString(node[0]) + "\n" +
                    Arrays.toString(node[1]) + "\n" +
                    Arrays.toString(node[2]) +  "\n👆";
        }
    }
}
